sign network social media relat user social media site reflect mixtur posit friendli neg antagonist interact contrast bulk research social network focus exclus posit interpret link peopl studi interplai posit neg relationship affect structur line social network connect analys theori sign network social psycholog find classic theori structur balanc captur common pattern interact odd fundament phenomena observ relat evolv direct natur line network develop altern theori statu explain observ edg sign insight underli social mechan work larg scale evalu theori sign network line dataset provid perspect reason social media site author keyword sign network structur balanc statu theori posit govern social media case studi wikipedia promot process social media site guid core group commit user engag form govern crucial aspect type govern deliber group reach decis issu import site crucial subtl role number promin social media site function investig delib aspect social media govern explor issu investig delib process extens public record promot wikipedia admin determin elect engag commit member wikipedia commun find group decis make heart process exhibit fundament form rel assess observ chanc voter support candid strongli depend relationship characterist voter candid investig individu voter decis elect outcom base model account sequenti public natur vote cite high impact infer network diffus influenc inform diffus viru propag fundament process talk place network directli observ node infect observ individu transmiss infect influenc typic difficult applic underli network diffus propag spread unobserv tackl challeng develop method trace path diffus influenc network infer network contagion propag time node adopt piec inform infect identifi optim network explain observ infect time optim problem np hard solv develop effici approxim algorithm scale larg dataset practic provabl optim perform demonstr effect approach trace inform cascad set million blog new articl year period infer inform flow onlin media space find diffus network new core peripheri structur small set core media site diffus inform rest web site tend stabl circl influenc gener new media site act connector multipl attribut graph model real dworld network larg scale real world network data social network internet web graph ubiquit studi social inform network seek find pattern explain emerg tractabl model network social network node rich set attribut ag gender exist network model focu model network structur ignor featur node present model refer multipl attribut graph mag natur captur interact network structur node attribut model node vector categor latent attribut probabl edg pair node depend product individu attribut attribut similar model yield mathemat analysi deriv threshold connect emerg giant connect compon show model rise graph constant diamet analyz degre distribut show model produc network log normal power law degre distribut depend condit empir comparison algorithm network commun detect detect cluster commun larg real world graph larg social inform network problem consider interest practic typic choos object function captur intuit network cluster set node intern connect extern connect appli approxim algorithm heurist extract set node relat object function good commun applic interest paper explor rang network commun detect method order compar understand rel perform systemat bias cluster identifi evalu common object function formal notion network commun examin class approxim algorithm aim optim object function addit simpli fix object approxim cluster size size resolv version optim problem commun qualiti function size finer len examin commun detect algorithm object function approxim algorithm obviou size depend behavior predict posit neg link onlin social network studi onlin social network relationship posit indic relat friendship neg indic relat opposit antagon mix posit neg link aris varieti onlin set studi dataset epinion slashdot wikipedia find sign link underli social network predict high accuraci model gener divers rang site model provid insight fundament principl drive format sign link network shed light theori balanc statu social psycholog suggest social comput applic attitud user estim evid provid relationship member surround social network sign network social media relat user social media site reflect mixtur posit friendli neg antagonist interact contrast bulk research social network focus exclus posit interpret link peopl studi interplai posit neg relationship affect structur line social network connect analys theori sign network social psycholog find classic theori structur balanc captur common pattern interact odd fundament phenomena observ relat evolv direct natur line network develop altern theori statu explain observ edg sign insight underli social mechan work larg scale evalu theori sign network line dataset provid perspect reason social media site author keyword sign network structur balanc statu theori posit predict posit neg link onlin social network studi onlin social network relationship posit indic relat friendship neg indic relat opposit antagon mix posit neg link aris varieti onlin set studi dataset epinion slashdot wikipedia find sign link underli social network predict high accuraci model gener divers rang site model provid insight fundament principl drive format sign link network shed light theori balanc statu social psycholog suggest social comput applic attitud user estim evid provid relationship member surround social network cite high impact empir comparison algorithm network commun detect detect cluster commun larg real world graph larg social inform network problem consider interest practic typic choos object function captur intuit network cluster set node intern connect extern connect appli approxim algorithm heurist extract set node relat object function good commun applic interest paper explor rang network commun detect method order compar understand rel perform systemat bias cluster identifi evalu common object function formal notion network commun examin class approxim algorithm aim optim object function addit simpli fix object approxim cluster size size resolv version optim problem commun qualiti function size finer len examin commun detect algorithm object function approxim algorithm obviou size depend behavior govern social media case studi wikipedia promot process social media site guid core group commit user engag form govern crucial aspect type govern deliber group reach decis issu import site crucial subtl role number promin social media site function investig delib aspect social media govern explor issu investig delib process extens public record promot wikipedia admin determin elect engag commit member wikipedia commun find group decis make heart process exhibit fundament form rel assess observ chanc voter support candid strongli depend relationship characterist voter candid investig individu voter decis elect outcom base model account sequenti public natur vote infer network diffus influenc inform diffus viru propag fundament process talk place network directli observ node infect observ individu transmiss infect influenc typic difficult applic underli network diffus propag spread unobserv tackl challeng develop method trace path diffus influenc network infer network contagion propag time node adopt piec inform infect identifi optim network explain observ infect time optim problem np hard solv develop effici approxim algorithm scale larg dataset practic provabl optim perform demonstr effect approach trace inform cascad set million blog new articl year period infer inform flow onlin media space find diffus network new core peripheri structur small set core media site diffus inform rest web site tend stabl circl influenc gener new media site act connector multipl attribut graph model real dworld network larg scale real world network data social network internet web graph ubiquit studi social inform network seek find pattern explain emerg tractabl model network social network node rich set attribut ag gender exist network model focu model network structur ignor featur node present model refer multipl attribut graph mag natur captur interact network structur node attribut model node vector categor latent attribut probabl edg pair node depend product individu attribut attribut similar model yield mathemat analysi deriv threshold connect emerg giant connect compon show model rise graph constant diamet analyz degre distribut show model produc network log normal power law degre distribut depend condit convex latent social network infer real world scenario imposs collect explicit social network data case network infer underli observ formul problem infer latent social network base network diffus diseas propag data contagion propag edg unobserv social network observ time node infect infect node infect time identifi optim network explain observ data present maximum likelihood approach base convex program penalti term encourag sparsiti experi real synthet data reveal method perfectli recov underli network structur paramet contagion propag model approach scale infer optim network thousand node matter minut supervis random walk predict recommend link social network kroneck graph approach model network network commun kroneck product number node cluster figur network network commun profil ncp plot emerg web onlin comput applic gave rise rich larg scale social activ data princip challeng build model understand structur larg social inform network present work cluster commun structur larg network cluster thought set node connect intern rest network find larg network cluster structur studi small social network graph embedd low dimension structur network million node tight cluster exist small size scale node larg size scale network expand network model base kroneck product effici model core peripheri network structur result suggest broader implic data analysi machin learn spars noisi high dimension social inform network intuit notion cluster qualiti fail tutori summari larg social inform network opportun ml model blog dynam blog produc post local underli mechan lead bursti tempor behavior observ blog network earlier work analyz network pattern blog found blog behavior bursti power law topolog tempor characterist intuit realist model introduc lead pattern focu work propos gener model simpl intuit principl individu blog produc tempor characterist blogospher global topolog network pattern power law degre distribut inter post time model zc cross approach base random walk combin power idea explor exploit make model simultan model topolog tempor dynam blogospher valid model experi larg collect blog million post meme dtrack dynam new cycl track topic idea meme web issu consider interest recent work develop method track topic shift long time scale abrupt spike appear name entiti approach suit identif content spread wide fade time scale order dai time scale perceiv new event develop framework track short distinct phrase travel intact line text develop scalabl algorithm cluster textual variant phrase identifi broad class meme exhibit wide spread rich variat daili basi princip domain studi show meme track approach provid coher represent new cycl daili rhythm new media long subject qualit interpret captur accur permit actual quantit analysi track million mainstream media site blog period month total million articl find set persist tempor pattern new cycl observ typic lag hour peak attent phrase new media blog diverg behavior peak heartbeat pattern handoff new blog develop analyz mathemat model kind tempor variat system exhibit shatterplot fast tool mine larg graph commun structur larg network natur cluster size absenc larg ddefin cluster monitor network evolut mdl abstract public titl author evolut scientif topic commun time commun shrunk emerg split time time turn point propos timefal automat answer question social network graph evolv time main novelti propos approach user defin paramet reli principl minimum descript length mdl extract commun find good cut point time commun chang abruptli cut point good lead shorter data descript illustr algorithm synthet larg real dataset show result timefal agre human intuit social network ahead microscop evolut social network present detail studi network evolut analyz larg onlin social network full tempor inform node edg arriv time larg scale studi individu node arriv edg creation process collect lead macroscop properti network methodolog base maximum likelihood principl investig wide varieti network format strategi show edg local plai critic role evolut network find supplement earlier network model base inher local preferenti attach base observ develop complet model network evolut node arriv prespecifi rate select lifetim node independ initi edg gap process select destin edg simpl triangl close model free paramet show analyt combin gap distribut node lifetim lead power law degre distribut accur reflect true network case final give model paramet set automat evolut gener realist synthet network arbitrari scale mobil call graph power dlaw lognorm distribut analyz massiv social network gather record larg mobil phone oper million user ten million call examin distribut number phone call custom total talk minut custom distinct number call partner custom find distribut skew significantli deviat expect power law lognorm distribut analyz observ distribut number call distinct call partner total talk time propos powertrack method fit lesser suitabl distribut doubl pareto lognorm dpln distribut data track paramet time powertrack find graph time consist gener process natur result dpln distribut observ show gener process lend natur appeal social wealth interpret context social network discuss applic result model forecast statist properti commun structur larg social inform network larg bodi work devot identifi commun structur network commun set node connect member remaind network paper character function size statist structur properti set node defin network commun profil plot character commun conduct measur wide rang size scale studi larg spars real world network wide rang applic domain result suggest significantli refin pictur commun structur larg real world network appreci previous strike find network dataset examin observ tight trivial commun small scale larger size scale commun gradual blend rest network commun behavior explain qualit level commonli network gener model behavior opposit expect base experi intuit expand graph graph embedd low dimension structur small social network serv testb commun detect algorithm found gener model edg ad iter forest fire burn process produc graph exhibit network commun structur similar observ planetari dscale view larg instant dmessag network present studi anonym data captur month high level commun activ microsoft messeng instant messag system examin characterist pattern emerg collect dynam larg number peopl action characterist individu dataset summari properti billion convers million peopl data construct commun graph million node billion undirect edg creat largest social network construct analyz date report multipl aspect dataset synthes graph find graph connect robust node remov investig planetari scale oft cite report peopl separ degre separ find averag path length messeng user find peopl tend commun similar ag languag locat cross gender convers frequent longer durat convers gender epidem threshold real network viru propag real network long disinfect network valu infect rate viru death rate singl node immun answer question essenti devis network wide strategi counter virus addit viral propag similar principl spread rumor inform fad impli solut viral propag offer insight problem set answer question develop nonlinear dynam system nld accur model viral propag arbitrari network includ real synthes network graph propos gener epidem threshold condit nld system prove epidem threshold network invers largest eigenvalu adjac matrix final show epidem threshold infect die exponenti rate epidem threshold model subsum threshold special case graph erd nyi ba powerlaw homogen demonstr predict power model extens experi real synthes graph show threshold condit hold arbitrari graph final show util threshold condit practic dictat node immun assess effect throttl commun structur larg network natur cluster size absenc larg ddefin cluster scalabl model real graph kroneck multipl larg real graph gener synthet graph match properti similar degre distribut similar small diamet similar spectrum propos kroneck graph natur obei properti present kronfit fast scalabl algorithm fit kroneck graph gener model real network naiv approach fit super exponenti time contrast kron fit take linear time exploit structur kroneck product sampl experi larg real synthet graph show kronfit mimic pattern found target graph fit model paramet result synthet graph anonym extrapol graph summar inform surviv threshold sensor network abstract network sensor node bluetooth enabl cell phone node transmit inform link node datum piec inform report emerg condit sensor network nation tradit song mobil phone viru node transmit datum datum surviv viru case condit viru die link node fault probabl import need ascertain surviv datum propos solv problem linear dynam system fix point stabil theorem provid closedform formula surprisingli depend addit paramet largest eigenvalu connect matrix illustr accuraci analysi realist real set mote sensor network intel mit gnutella network cost deffect outbreak detect network network spread diseas product recommend diffus social network fundament process social network behavior cascad node node epidem new opinion rumor fad urban legend word mouth effect market rise websit free web base servic viru diseas propag chang social prioriti smoke recycl satur new coverag topic diffus blogger internet energ polit campaign cascad failur financi market local effect riot peopl walk lectureempir studi diffus experiment studi diffus long histori spread agricultur practic ryan gross adopt hybrid corn farmer iowa classic studi diffus interperson network plai import role adopt diffus social process spread medic practic coleman al studi adopt drug doctor illinoi clinic studi scientif evalu suffici convinc doctor social power peer led adoptiondiffus network initi node activ activ node spread influenc node web project learn contextu subgraph web graphic relationship web page leverag sourc inform method rank search result date specif graphic properti analys introduc web project methodolog gener prior effort exploit graphic relationship web wai approach creat subgraph project set page domain larger web graph machin learn construct predict model graphic properti evid describ method present experi illustr construct predict model search result qualiti user queri reformul pattern cascad behavior larg blog graph blog cite influenc link evolv popular blog post drop exponenti time question address work blog weblog import medium inform time public eas wide avail fact make headlin discuss discov evid polit event fact blog link creat publicli record inform influenc spread underli social network aggreg link blog post creat direct graph analyz discov pattern inform propag blogspac understand underli social network report surpris find blog link inform propag structur analyz largest dataset blog million blog post analysi shed light rumor virus idea propag social comput network web project learn contextu subgraph web graphic relationship web page leverag sourc inform method rank search result date specif graphic properti analys introduc web project methodolog gener prior effort exploit graphic relationship web wai approach creat subgraph project set page domain larger web graph machin learn construct predict model graphic properti evid describ method present experi illustr construct predict model search result qualiti user queri reformul dynam viral market present analysi person person recommend network consist million peopl made million recommend half million product observ propag recommend cascad size explain stochast model establish recommend network grow time ectiv viewpoint sender receiv recommend averag recommend ectiv induc purchas spread product price categori viral market ectiv dynam viral market present analysi person person recommend network consist million peopl made million recommend half million product observ propag recommend cascad size explain stochast model establish recommend network grow time ectiv viewpoint sender receiv recommend averag recommend ectiv induc purchas spread product price categori viral market ectiv data associ topic intens track present unifi model tradition view separ task data associ intens track multipl topic time data associ part task assign topic class data point intens track part model burst intens topic time sampl larg graph huge real graph deriv repres sampl algorithm comput interest measur shortest path central between impract larg graph graph sampl essenti pattern influenc recommend network inform cascad phenomena individu adopt action idea due influenc process spread underli social network result widespread adopt inform cascad context recommend studi pattern cascad recommend aris larg social network investig larg person person recommend network consist million peopl made sixteen million recommend half million product dataset pose number fundament question kind cascad aris frequent real life featur distinguish enumer count cascad subgraph larg direct graph compon develop effici heurist base graph isomorph test scale larg dataset discov pattern distribut cascad size approxim heavi tail cascad tend shallow occasion larg burst propag occur rel abund di erent cascad subgraph suggest subtl properti underli social network recommend process gmine system scalabl interact graph visual mine graph visual tool exist handl larg graph interact interest larg graph hundr thousand node graph bring challeng straightforward interact manipul prohibit slow sensori overload plot replot graph quickli user overwhelm vast volum inform screen clutter node edg overlap gmine system address issu summar multi resolut gmine offer multi resolut graph explor partit graph hierarchi commun commun store tree structur tree gmine offer summar implement innov subgraph extract algorithm visual output impact linguist analysi semant graph coverag learn document extract automat document summar problem creat document surrog adequ repres full document content aim summar system replic qualiti summari creat human paper investig machin learn method extract full sentenc document base document semant graph structur explor support vector machin svm learn method affect qualiti linguist analys semant graph represent appli type linguist analysi simpl part speech tag noun phrase verb full logic form analysi identifi subject predic object tripl build semant graph train svm classifi identifi summari node node extract sentenc experi duc cast dataset show svm base extract sentenc differ significantli simpl sophist syntact analysi case graph attribut learn essenti classifi perform qualiti extract summari graph time densif law real graph evolv time normal growth pattern social technolog inform network studi discov pattern static graph identifi properti singl snapshot larg network small number snapshot includ heavi tail degre distribut commun small world phenomena lack inform network evolut long period hard convert find statement trend time studi realist vast bodi theoret research focus overli simplist model parallel comput notabl pram overli specif model repres real world kind model encourag exploit formal loophol reward develop techniqu yield perform rang current futur parallel machin paper offer parallel machin model call logp reflect critic technolog trend underli parallel comput intend serv basi develop fast portabl parallel algorithm offer guidelin machin design model strike balanc detail simplic order reveal import bottleneck make analysi interest problem intract model base paramet abstractli comput bandwidth commun bandwidth commun delai effici coupl commun comput portabl parallel algorithm typic adapt machin configur term paramet util model demonstr exampl implement cm dynam viral market present analysi person person recommend network consist million peopl made million recommend half million product observ propag recommend cascad size explain stochast model establish recommend network grow time ectiv viewpoint sender receiv recommend averag recommend ectiv induc purchas spread product price categori viral market ectiv model link qualiti sensor network sensor network ad hoc wireless network small low cost sensor measur characterist environ autonom low cost sensor limit batteri life prone failur commun loss import devis effici power usag commun messag rout scheme work concentr estim link qualiti pair sensor natur environ estim basic compon algorithm optim power radio transmiss signal commun schedul rout scheme result show simpl regress model give estim error show dimension reduct techniqu understand topolog commun network identifi potenti bottleneck network povzetek uporabo metod za zmanj anj dimenzij podatkov nelinearnih modelov omr ju senzorjev je mo dose zmanj anj napak za download estim task kdd cup paper describ work download estim task kdd cup task requir estim time paper download dai publish arxiv org preprint server paper physic relat area train data consist approx paper full text metadata graph citat paper inform download subset paper number download timestamp individu download approach base extens bag word model linear svm regress learn algorithm describ experi kind featur help useless focu issu featur weight turn import task linear program boost uneven dataset paper extend notion linear program boost handl uneven dataset extens experi text classif problem compar perform number di erent boost strategi concentr problem pose uneven dataset download estim task kdd cup paper describ work download estim task kdd cup task requir estim time paper download dai publish arxiv org preprint server paper physic relat area train data consist approx paper full text metadata graph citat paper inform download subset paper number download timestamp individu download approach base extens bag word model linear svm regress learn algorithm describ experi kind featur help useless focu issu featur weight turn import task 